#include<bits/stdc++.h>
using namespace std;
int main(){
	long long n;
	cin >> n;
	for(int i = 1 ; i <= n ; i++){
		long long k;
		char a[10];
		long long l = 0 , p = 1, len;
		cin >> k >> a;
		len = strlen(a);
		for(long long i = len - 1 ; i >= 0 ; i--){
			if(a[i] <= '9') l += (a[i] - '0') * p;
			else l += (a[i] - 'A' + 10) * p;
			p *= k;
		}
		cout << l << endl;
	}
	return 0;
}
